In digital signal processing, serial/parallel multiplication is usually performed with a radix of 2. This means that one operand is held in a parallel register while the other operand is broadcast one bit at a time. Partial products are formed by cross multiplication of the stored operated with the broadcast bit and are shift-accumulated to form the full product of the two operands. Normally all arithmetic is 2's complement.
The expression "radix-2" corresponds to one bit because the logarithm to the base 2 of 2 is unity. More generally, the radix X represents a cluster of N bits, where N is equal to the logarithm to the base 2 of X. Thus radix-4 represents a cluster of 2 bits, radix-8 represents a cluster of 3 bits and so on.
It is known, for example from Smith & Denyer, "Serial-Data Computation", Kluwer Academic Publishers, 1988, and also Ercegovac et. al. "An Area-Efficient VLSI Design of a Radix-4 Multiplier", IEEE-ICCD 1983, pages 684-687, to provide a radix-4 multiplier in which a modified-Booth recoding algorithm is employed to recode broadcast digits as signed quantities. Partial products may be formed by a combination of shifting, gating and inversion and the partial products may be shift-accumulated to form the full product. It is not usually beneficial to perform such recoding in radix-2 operation, which corresponds to the original Booth algorithm, and the equivalent recoding using a higher radix is inappropriate in serial/parallel multipliers, because the formation of partial products then requires multiplicative operations.
There are circumstances in which it is desirable to employ a digit size, that is to say the number of bit per digit, which is greater than 2. One example is given by the methods of realizing digital signal processors using a programmed compiler disclosed in our prior copending U.S. Pat. application Ser. No. 425634 filed 23 Oct. 1989, the disclosure of which is incorporated herein by reference. In the compiler and compilation methods described in tat earlier copending application, we disclose the use of "bits", "digits" and "subwords" as fundamental architectural attributes in automatic synthesis of digital signal processors. The term "bits" is used therein to refer to the ratio bits/digit and the term "digits" refers to the ratio of digits/subword. The quantity "subword" is used to refer to the ratio subwords/word, the product of the three attributes being the length of a digital word in bits. Individually, the number of bits per digit affects the maximum clock rate because sum and carry ripple path lengths are proportional to this attribute. In every design, "bits" is determined by appropriately factoring the word size, using the application task rate and a technology-specific component. The quantities "bits" and "digits" are global throughout the processor which is to be realized whereas the attribute "subwords", which determines the pipelining required from place to place in the processor, is a local attribute.
In order to facilitate realization of a digital signal processor, it is for reasons apparent from a consideration of our prior copending application No. 425634 and otherwise desirable to be able to operate at a digit size, namely the number of bits per digit, greater than 2. Digit sizes of up to 8, corresponding to a radix of 256, may be desirable and occasionally larger digit sizes may be required. However, a digit size greater than 2 corresponds to a radix greater than 4 and, as has been noted above, it is not desirable to employ such higher radix recoding for serial/parallel multipliers.